package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/19
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode node = create();
        TreeNode node1 = lowestCommonAncestor(node, node.left, node.left.right.right);
        System.out.println(node1);
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(3);
        ret.left = new TreeNode(5);
        ret.left.left = new TreeNode(6);
        ret.left.right = new TreeNode(2);
        ret.left.right.left = new TreeNode(7);
        ret.left.right.right = new TreeNode(4);
        return ret;
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if ( root == null || root == p || root == q )
            return root;
        TreeNode lef = lowestCommonAncestor(root.left, p, q);
        TreeNode rig = lowestCommonAncestor(root.right, p, q);
        if ( lef == null )
            return rig;
        else if ( rig == null )
            return lef;
        else
            return root;
    }

}
